Electronic Batcher Banyan networks are known.
A Banyan network is a self routing network. That is, a packet sent across the Banyan network reaches its correct, desired destination without the need for an additional controller. Each packet that is input to the Banyan network contains sufficient information, e.g. in a header, to be able to route the packet to its desired destination based on an analysis of the information at component switches within the Banyan network.
Referring to FIG. 1 (prior art), a 2×2 Banyan switch 10 is shown—i.e. it has 2 inputs and 2 outputs. The switch 10 is a component switch in a Banyan network, and reads the relevant bit, e.g. the most significant bit (MSB), in a destination tag contained in a header of a packet being sent across the Banyan network. When the packet is being processed through the switch 10, if the MSB is 0, the packet is routed to the first output. If the MSB is 1, the packet is routed to the second output.
An n×n Banyan network can be constructed from log 2n layers of switches. Thus, a packet sent through an n×n Banyan network should have log 2n bits in its destination tag. The switch 10 reads the relevant bit in the destination tag. For example, this may be the MSB in a first stage of the n×n Banyan network followed by the next MSB (i.e., MSB-1) at the next stage and so on.
A problem associated with component switches within a Banyan network is that two packets having the same relevant bit, e.g. MSB, can overlap at a particular component switch. For example, the packets can arrive at the inputs of the switch 10 at the same time. When the switch 10 tries to send both packets to the same output, a collision occurs. As a result data can be lost. It is known to pre-sort packets prior to processing through a Banyan network. The packets are pre-sorted according to their destination tag information.
This pre-sorting can be carried out by a Batcher network (electronic Batcher networks are known). A Batcher network comprises component switches (see FIG. 2), which interrogate the destination tag of 2 incoming packets, for example, and compare them. A packet having a higher value destination tag is routed to the first output and a packet having a relatively low value destination tag is routed to the second output.
When a Batcher network is employed to sort packets prior to a Banyan network, the networks are usually both of the same size. For example, a 4×4 Batcher network will precede a 4×4 Banyan network.
The Batcher network will sort the data packets into an order, which avoids collisions as the packets are processed through the Banyan network. Thus a Batcher Banyan network is provided.